package club.xiaojiawei.monotonestack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/12/22 6:32 PM
 * @question 84. 柱状图中最大的矩形、、
 * @description 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class LargestRectangleArea84 {

    public static void main(String[] args) {
        LargestRectangleArea84 test = new LargestRectangleArea84();
        int result = test.largestRectangleArea2(new int[]{2, 1, 5, 6, 2, 3});
        System.out.println(result);
    }

    /**
     * 官方-单调栈
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

    /**
     * 官方-单调栈+常数优化
     * @param heights
     * @return
     */
    public int largestRectangleArea2(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() &&  heights[i] <= heights[mono_stack.peek()]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

    /**
     * 民间-单调栈
     * @param heights
     * @return
     */
    public int largestRectangleArea3(int[] heights) {
        int len = heights.length, area = 0, top = 0, top_value;
//        模拟栈
        int[] stack = new int[len + 1], index = new int[len + 1];
        for (int i = 0; i < len; i++) {
            while (heights[i] < stack[top]) {
                top_value = stack[top];
                while (stack[--top] >= top_value){
                    area = Math.max(area, top_value * (i - index[top]));
                }
            }
            stack[++top] = heights[i];
            index[top] = i + 1;
        }
        while (stack[top] > 0) {
            top_value = stack[top];
            while (stack[--top] >= top_value){
                area = Math.max(area, top_value * (len - index[top]));
            }
        }
        return area;
    }

    /**
     * 官方-dp
     * @param heights
     * @return
     */
    public int largestRectangleArea4(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] maxRightIndex = new int [length];
        // 记录左边第一个小于该柱子的下标
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
            int t = i - 1;
            // 这里不是用if，而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子 右边第一个小于该柱子的下标
        maxRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = maxRightIndex[t];
            maxRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < length; i++) {
            int sum = heights[i] * (maxRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }

    /**
     * 官方-单调栈+常数优化(栈优化)
     * @param heights
     * @return
     */
    public int largestRectangleArea5(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        int[] stack = new int[n];
        int index = -1;
        for (int i = 0; i < n; ++i) {
            while (index != -1 &&  heights[i] <= heights[stack[index]]) {
                right[stack[index]] = i;
                index--;
            }
            left[i] = (index == -1 ? -1 : stack[index]);
            stack[++index] = i;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}
